#include <bits/stdc++.h>

using namespace std;
#define int long long
const int inf = 0x3f3f3f3f3f3f3f3f;

void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    int ans1 = 0, ans2 = 0;
    // 01010
    string s1 = s;
    int cnt = 0;
    for (int i = 0; i < n - 1; i++)
    {
        if (s1[i] != cnt + '0')
        {
            s1[i] = s1[i] == '0' ? '1' : '0';
            s1[i + 1] = s1[i + 1] == '0' ? '1' : '0';
            ans1++;
        }
        cnt ^= 1;
    }
    if (s1[n - 1] == s1[n - 2]) ans1 = inf;
    // 10101
    cnt = 1;
    string s2 = s;
    for (int i = 0; i < n - 1; i++)
    {
        if (s2[i] != cnt + '0')
        {
            s2[i] = s2[i] == '0' ? '1' : '0';
            s2[i + 1] = s2[i + 1] == '0' ? '1' : '0';
            ans2++;
        }
        cnt ^= 1;
    }
    if (s2[n - 1] == s2[n - 2]) ans2 = inf;
    if (ans1 == inf && ans2 == inf) cout << -1 << endl;
    else cout << min(ans1, ans2) << endl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int _ = 1;
    cin >> _;
    while (_--)
    {
        solve();
    }
    return 0;
}